package 双指针技巧与相关题目;

// 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water/

public class Code03_TrappingRainWater {

    // 辅助数组的解法（不是最优解）
    // 时间复杂度O(n)，额外空间复杂度O(n)
    // 提交时改名为trap
    public static int trap1(int[] height) {
        int n = height.length;
        // 0-i位置的最大值
        int[] lmax = new int[n];
        // i-n-1位置的最大值
        int[] rmax = new int[n];
        lmax[0] = height[0];
        // 0~i范围上的最大值，记录在lmax[i]
        for (int i = 1; i < n; i++) {
            lmax[i] = Math.max(lmax[i - 1], height[i]);
        }
        rmax[n - 1] = height[n - 1];
        // i~n-1范围上的最大值，记录在rmax[i]
        for (int i = n - 2; i >= 0; i--) {
            rmax[i] = Math.max(rmax[i + 1], height[i]);
        }
        int ans = 0;
        //   x               x
        //   0  1 2 3...n-2  n-1
        // 第0位置一定接不到雨水，第n-1位置也一定接不到雨水
        // 只统计 1 ~ n-2 位置能接多少雨水
        for (int i = 1; i < n - 1; i++) {
            ans += Math.max(0, Math.min(lmax[i - 1], rmax[i + 1]) - height[i]);
        }
        return ans;
    }

    public static int trap(int[] height) {
        // l从1 位置开始，因为0位置是接不到水量的
        int l = 1;
        // r从n-2 位置开始，因为 n-1 位置是接不到水量的
        int r = height.length - 2;
        // 0 ~ l-1 位置 左部分的最大值
        int lmax = height[0];
        // r-1 ~ n-1 位置 右部分的最大值
        int rmax = height[height.length - 1];
        int ans = 0;
        while (l <= r) {
            // 左侧部分的最大值 <= 右侧部分的最大值，先结算l位置的水量
            if (lmax <= rmax) {
                ans += Math.max(0, lmax - height[l]);
                // 更新左侧部分的最大值，然后l++
                lmax = Math.max(lmax, height[l++]);
            } else {
                ans += Math.max(0, rmax - height[r]);
                // 更新右侧部分的最大值，然后r--
                rmax = Math.max(rmax, height[r--]);
            }
        }
        return ans;
    }
}
